package backtrack

/*
1、回溯算法理论基础
回溯法也叫回溯搜索法，是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。
所以回溯函数也就是递归函数，指的是一个函数。

回溯并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，
如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

组合是不强调元素顺序的，排列时强调元素顺序的！

回溯函数模板：
1、命名backtracking,返回值为空，参数要跟胡逻辑来写，需要什么参数就填什么参数
2、回溯函数终止条件：一般时找到满足条件的一条答案，把这个答案存放起来，并结束本层递归。
3、回溯搜索的遍历过程：一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成树的深度。
*/

// 回溯算法模板框架
// func backtracking(参数) {
//     if (终止条件) {
//         存放结果
//         return
//     }

//     for (选择：本层集合中元素 树中节点孩子的数量就是集合的大) {
//         处理节点;
//         backtracking(路径，选择列表); // 递归
//         回溯，撤销处理结果
//     }
// }
